1. Field of the Invention
The present invention relates generally to a decoding apparatus and method in a communication system. More particularly, the present invention relates to an apparatus and method for decoding low density parity check (LDPC) codes.
2. Description of the Related Art
Conventionally, communication systems do not transmit raw data, but transmit coded data after performing a coding operation. Coding schemes are classified into an iterative coding scheme, a convolution coding scheme, a turbo coding scheme, and a low density parity check (LDPC) coding scheme. Each coding scheme can be used according to its characteristics. A large amount of research is being done on the LDPC coding scheme for use in next generation mobile communication systems.
The LDPC coding scheme is a type of block coding using a coding matrix prior to transmitting information bits. When block coding is performed, the LDPC coding scheme uses a coding matrix including all 1's except for a sparse number of 0's. The LDPC coding scheme uses a parity check matrix configured by rows and columns having a sparse number of 0's. The parity check matrix can be expressed by a code structure using a factor graph in which the rows and columns are mapped to check nodes and variable nodes.
Since their block size is large, LDPC codes have a minimum distance and a low frame error rate as compared with turbo codes. In the case of the LDPC codes, an error floor does not appear at a relatively high signal to noise ratio (SNR). An error detection process can be performed for a decoded codeword and a decoding process can be efficiently stopped, by using the orthogonality of a codeword and a parity check matrix without cyclic redundancy check (CRC).
These LDPC codes can replace turbo codes in the next generation mobile communication system, due to factors such as a parallel structure and low complexity associated with implementation of a decoder, and a low error floor and good frame error rate associated with the performance of a decoder. With continued extensive research into LDPC codes, LDPC codes having excellent characteristics will appear in the future.
Flarion has developed a novel LDPC code design and hardware (H/W) implementation, and has proposed multi-edge type vector LDPC codes that can have an excellent frame error rate as compared with turbo codes in terms of a relatively short length and can implement a parallel structure decoder. The LDPC implementation is focused on an efficient memory design and decoding rate improvement.
FIGS. 1A and 1B illustrate a conventional propagation decoding scheme that is a type of sum product algorithm.
Referring to FIG. 1A, one check node processor is connected to a plurality of variable node processors. The connection between the check node processor and the variable node processors has a parity check matrix structure. A variable node processor is a node to which an initially received symbol is input.
Received symbols are first stored in memories coupled to inputs of the variable node processors. The check node processor computes a probability value of a current node symbol from neighboring probability values after reading probability values that are output from the variable node processors and are stored in the memories. A probability value of a symbol computed by the check node processor is overwritten to a memory.
The variable node processor reads a probability value from a memory to compute the last soft metric (or log-likelihood ratio (LLR)), and stores the computed soft metric in the memory. An iterative computation process between the check and variable node processors is performed such that reliability is improved. Each of the check and variable node processors reads a value from a memory block corresponding to 1 in columns and rows of the parity check matrix, performs a predetermined computation, and stores a computation result.
Referring to FIG. 1B, one variable node processor is connected to a plurality of check node processors. The connection between each check node processor and the variable node processor has a parity check matrix structure.
A memory block is provided such that a memory storing a reliability value of a symbol in each node can be easily configured by hardware. Numbers illustrated in FIGS. 1A and 1B denote different nodes, and an arrow direction denotes the flow of a probability value associated with a reliability value.
FIG. 2 illustrates a conventional parity check matrix and a Tanner graph corresponding thereto.
A parity check matrix H associated with a conventional block code is configured by a large number of 1's. In this matrix, the number of 1's is large. Accordingly, a decoding process can be performed with high reliability. In the case of an iterative decoding structure, desired performance can be obtained through a small number of iterative decoding processes. Here, a ‘1’ value indicates a node connection. Accordingly, when the number of 1's is large, it indicates that a large amount of referable information is present. In this case, an accurate symbol value can be determined. If the number of nodes is large when a determination is made as to whether a symbol is 1 or 0, an accurate probability value can be computed.
Referring to FIG. 2, one check node processor is connected to six variable node processors. However, as the number of nodes increases, the amount of hardware must increase and hence implementation complexity increases in limited applications such as mobile communication.
When node processors are implemented in a non-parallel structure, an LDPC decoder does not have lower complexity than a turbo decoder. In this case, a decoding rate becomes low. Because one check node processor and variable node processors must compute probability values of all received symbols, significant time is required to compute the probability values. However, when the node processors are designed such that they are implemented in a parallel structure to complete all computations at the same time, complexity becomes high. Accordingly, a trade-off is required in applying the parallel structure to a specific system. That is, a suitable parallel structure between the node processors reduces complexity, but degrades the decoding rate. When the LDPC decoder is designed in a partial parallel structure rather than a total parallel structure, control of a memory block becomes complex. A need exists for efficient memory control in a trade-off process between hardware performance and implementation complexity.